#include "mylist.hpp"
#include <vector>

class VirtualMemPageReplace {
private:
    const int AllPageNum = 20;
    const int PageNum = 3;
    using Iterator = MyList::list<int>::iterator;

    void init() {
        for (int i = 0; i < PageNum; i++)
            _pages.push_back(-1);

        for (int i = 0; i < AllPageNum; i++) {
            int num = rand() % 10;
            _sequence.emplace_back(num);
        }
        std::cout << "Page sequence: ";
        for (auto num : _sequence)
            std::cout << num << " ";
        std::cout << "\n";
    }

    // 若命中，则返回迭代器和true
    // 若没有命中，则返回需要淘汰的位置和false
    std::pair<Iterator, bool> find(size_t AllPageNum) {
        auto it = _pages.begin();
        for (; it != _pages.end(); ++it) {
            if (*it == AllPageNum || *it == -1)
                return {it, true};
        }
        // 拿出队首元素
        return {_pages.begin(), false};
    }

    void showWorkingSet() {
        for (auto num : _pages)
            std::cout << num << " ";
    }

    void AdjustPageLocation(std::pair<Iterator, bool>& location) {
        int num = *location.first;
        // 查看当前物理内存中是否还存在-1元素
        // 若还有则将其调入到-1元素前
        // 若没有直接插入到最后
        _pages.erase(location.first);
        auto it = _pages.begin();
        for (; it != _pages.end(); ++it) {
            if (*it == -1)
                break;
        }
        if (it == _pages.end())
            _pages.push_back(num);
        else
            _pages.insert(it, num);
    }

    void LRU() {
        printf("   SeqID        Working Set\n");
        for (int i = 0; i < AllPageNum; i++) {
            // 直接进行分配
            printf("   %5d        ", i);

            // 选出最小的进行分配
            std::pair<Iterator, bool> location = find(_sequence[i]);
            if (location.second == true) {
                // 将命中的取出，放在最后一个位置
                if (*location.first != -1) {
                    _hitnum++;
                    AdjustPageLocation(location);
                    showWorkingSet();
                    std::cout << "   *hit*" << "\n";
                } else {
                    *location.first = _sequence[i];
                    showWorkingSet();
                    std::cout << "\n";
                }
                continue;
            }
            // 未命中，将第一个删除，然后插入新元素
            _pages.pop_front();
            _pages.push_back(_sequence[i]);
            showWorkingSet();
            std::cout << "\n";
        }
    }

    void calPFR() {
        printf("Hit = %zd, Miss = %zd\n", _hitnum, AllPageNum - _hitnum);
        float pfr = 0.1 * (AllPageNum - _hitnum) / AllPageNum;
        printf("Page fault Rate = %zd/%d = %lf\n", AllPageNum - _hitnum, AllPageNum, pfr);
    }

public:
    VirtualMemPageReplace()
        : _hitnum(0)
    {}

    void start() {
        srand(time(0));
        init();
        LRU();
        calPFR();
    }
    
private:
    std::vector<size_t> _sequence;
    MyList::list<int> _pages;
    size_t _hitnum;
};

int main() {
    VirtualMemPageReplace vmpr;
    vmpr.start();

    return 0;
}
